package search.util;

import static org.junit.Assert.assertEquals;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Random;

import org.junit.Test;

public abstract class AbstractTreeAlgorithmsTest {
    private Tree<Integer> root;
    protected ITreeAlgorithms<Integer> algo;

    private Random rdm = new Random();

    @Test
    public void testCountEmptyTree() {
        assertEquals(0, algo.numberOfNodes(null));
    }

    @Test
    public void testCountOneNode() {
        assertEquals(1, algo.numberOfNodes(new Tree<Integer>(0)));
    }

    @Test
    public void testCountSomeNodes() {
        root = new Tree<Integer>(0);
        for (int i = 0; i < 4; i++)
            root.addValue(null);
        assertEquals(5, algo.numberOfNodes(root));
    }

    @SuppressWarnings("unchecked")
    @Test
    public void testCountRandomNumberOfNodes() {
        int numberOfNodes = 1;
        root = new Tree<Integer>(0);
        int size1 = rdm.nextInt(5);
      
        Tree<Integer>[] firstGeneration = new Tree[size1];
        for (int i = 0; i < size1; i++) {
            firstGeneration[i] = root.addValue(0);
            numberOfNodes++;
            int size2 = rdm.nextInt(5);
     
            for (int j = 0; j < size2; j++) {
                Tree<Integer> secondGeneration = firstGeneration[i].addValue(0);
                numberOfNodes++;
                if (rdm.nextInt(2) == 1) {
                    secondGeneration.addValue(null);
                    numberOfNodes++;
                }
            }
        }
        assertEquals(numberOfNodes, algo.numberOfNodes(root));
    }

    @Test
    public void testPathToGoal() {
        Tree<Integer> root = buildTestTree();
        List<String> pathList = buildPathList();
        List<String> computedList = algo.getPathToGoal(root, 22);
        assertEquals("die Liste hat die falsche Laenge,", pathList.size(),
                computedList.size());
        Iterator<String> testIter = computedList.iterator();
        for (String template : pathList) {
            String found = testIter.next();
            assertEquals("Element ist falsch,", template, found);
        }
    }

    private List<String> buildPathList() {
        List<String> pathList = new ArrayList<String>();
        pathList.add("0");
        pathList.add("12");
        pathList.add("22");
        return pathList;
    }

    private Tree<Integer> buildTestTree() {
        Tree<Integer> root = new Tree<Integer>(0);
        root.addValue(10);
        Tree<Integer> child1 = new Tree<Integer>(11);
        root.addChild(child1);
        Tree<Integer> child2 = new Tree<Integer>(12);
        root.addChild(child2);
        child1.addValue(20);
        child1.addValue(21);
        child2.addValue(22);
        return root;
    }
}